The problem of Quality of Service (QoS) provisioning in packet-switched networks has been a focus of networking and telecommunication research communities. Many new packet scheduling algorithms, such as Virtual Clock (VC) and Weighted Fair Queueing (WFQ), have been proposed for the support of QoS guarantees. For example, it has been shown that in a network where WFQ schedulers (or VC schedulers) are employed at every router, end-to-end delay and bandwidth guarantees can be supported for each user traffic flow. Using these results as a reference model, the Internet Engineering Task Force (IETF) has defined a guaranteed service under its Integrated Services or IntServ architecture, where end-to-end delay and bandwidth guarantees are provided for users on a per-flow basis. To support the IETF IntServ architecture, a signaling protocol, RSVP, for setting up end-to-end QoS reservation along a flow's path has also been proposed and standardized.
Performing per-flow management inside the network, however, raises the important issue of scalability. Because of the complexity of per-flow operations both in the data plane and QoS control plane, the IntServ architecture may not scale well with the increasing size of the Internet. As an alternative to per-flow based QoS provisioning, in recent years a different paradigm, the Differentiated Services or DiffServ, has been proposed and defined by the IETF. By processing packets based on a number of pre-specified Per-Hop Behaviors (PHBs) encoded by bit patterns carried inside a packet header, the DiffServ paradigm greatly simplifies the data plane of the network core of a domain, thereby making it more scalable. (We will refer to these bit patterns, or the PHBs they embody, as the packet state.) End-to-end, user-to-user QoS support is provided through intra-domain QoS provisioning and inter-domain service agreement. These control plane functions can be performed, for example, by employing a bandwidth broker architecture. On the other hand, the DiffServ architecture, as it is currently defined, aims to provide only coarse-grain QoS support to users. It remains to be seen whether such a service model would be sufficient to meet the potentially diverse user QoS requirements in the future. Furthermore, many issues regarding the design of bandwidth brokers such as admission control and QoS provisioning still need to be addressed, both theoretically and in practice.
The DiffServ paradigm has been extended using the notion of dynamic packet states to include several techniques to support end-to-end per-flow delay guarantees without per-flow QoS management. In the data plane, a (non-work-conserving) scheduling algorithm, called Core Jitter Virtual Clock or CJVC, provides end-to-end per-flow delay guarantees without per-flow scheduling states at core routers. (Such scheduling algorithms are referred to as core-stateless, in contrast to the conventional stateful scheduling algorithms such as VC or WFQ, where certain scheduling states must be maintained for each flow.) In the control plane, an aggregate reservation estimation algorithm is designed which eliminates the need of maintaining per-flow QoS reservation states. Instead, an aggregate QoS reservation state is maintained at each core router. A hop-by-hop signaling protocol, however, is still needed to set up QoS reservation for each flow along its path within a domain.
The Internet backbone is facing two problems simultaneously: (1) there is a need to introduce guaranteed QoS, and (2) there is a need for faster switching infrastructure. The first problem may be solved by building switches using output-queuing. This approach is known to achieve the throughput of the switch to 100%. Furthermore, powerful scheduling algorithms, for example WFQ, may be placed at the output port and thus provide QoS guarantee. But output queuing for an N×N switch may require the switching fabric and memory to run N times as fast as the line rate. Thus it may be impractical to design high speed switches, for example a terabit switch, since memories with sufficient bandwidth are simply not available at such high speed.
To build faster switches, an Input-Queued (IQ) switch architecture may be employed since the fabric and memory of an IQ switch need only run as fast as the line rate. Furthermore, it has been shown that by using a scheme known as Virtual Output Queuing (VOQ), it is possible to eliminate entirely the so-called Head-Of-Line (HOL) blocking problem associated with an IQ switch. However, it remains to be seen how an IQ switch without any speedup can guarantee QoS.
It is possible to use a combined input and output port queued (CIOQ) switch with a small speedup, termed S, (e.g., 2-4) to provide guaranteed QoS. Under such an architecture, buffers are employed at both the input ports and output ports and the switch can remove up to S (1_<S<_N) packets from each input and deliver up to S packets to each output within a time slot, where a time slot is the time between packet arrival at input ports. With a small speedup, for example, 2 to 4 time, a CIOQ switch may behave identically to an OQ switch for all types of traffic. Herein, “behave identically” is defined as when the same inputs are applied to both the OQ switch and to the CIOQ switch, the corresponding output processes from the two switches are completely indistinguishable.
Although there are processes that enable a CIOQ switch with a small speedup to mimic an OQ switch with WFQ scheduling algorithm, in practice, such processes may not be implementable for the following two problems: the processes are not scalable (and thus not feasible) to maintain per-flow QoS state in a high speed CIOQ switch to mimic an OQ switch with WFQ scheduler; and even if it were feasible to maintain per-flow state at the CIOQ switch, the calculation of departure time for scheduling in a CIOQ switch requires complex communication among various input and output ports, which is simply not implementable for a switch operating at very high speed. Therefore, there is a need to design an implementation-friendly scheduling algorithm for a CIOQ switch to guarantee QoS.